package com.linzm.leetcode.primary.exercises3_20230122;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author zimingl
 * @Date 2023/1/23 15:43
 * @Description: 最长回文串
 */
public class Demo4_409 {
    /**
     * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
     * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
     *输入:s = "abccccdd"
     * 输出:7
     * 解释:
     * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
     */
    public static void main(String[] args) {
        Demo4_409 demo4_409 = new Demo4_409();
        String s = "abccccdd";
        int longestPalindrome = demo4_409.longestPalindrome(s);
        System.out.println(longestPalindrome);
    }

    private int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            int count = map.getOrDefault(s.charAt(i), 0) + 1;
            map.put(s.charAt(i), count);
        }
        int sum = 0;
        for (Integer num : map.values()) {
            if (num % 2 != 0) {
                flag = true;
            }
            sum += num / 2;
        }
        sum *= 2;
        if (flag) {
            sum += 1;
        }
        return sum;
    }

    private int longestPalindrome2(String s) {
        int[] count = new int[52];
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            char c = s.charAt(i);
            count[c]++;
        }

        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }
}
